#include <iostream>
#include <limits.h>
#include <algorithm>
#include "SortTestHelper.h"
#include "Student.h"


using namespace std;

template<typename T>
void selectionSort(T arr[] , int n ){

    for(int i = 0 ; i < n ; i++){

        //寻找[i ,  n ] 区间里的最小值
        int minIndex = i ;
        for ( int j = i + 1 ; j < n ; j++){
            if ( arr[j] < arr[minIndex])
                minIndex = j ;
        }
        swap( arr[i] , arr[minIndex]);
    }

}

template <typename T>
void insertSort(T arr[], int n){

    for(int i = 1 ; i < n ; i++){

        //1.  没有优化的
//        for(int j=i ; j > 0 ; j--){
//
//            //寻找元素arr[i]合适的位置
//            if (arr[j]<arr[j-1]){
//                swap(arr[j],arr[j-1]);
//            }else{
//                break;
//            }
//        }
        //  没有优化的
//        for(int j=i ; j > 0 & arr[j]<arr[j-1] ; j--){
//            //寻找元素arr[i]合适的位置
//                swap(arr[j],arr[j-1]);
//
//        }

        //2.优化 更改，复制一个复本保存要插入的元素，用赋值代替交换位置(每一次交换有三次赋值)，减少交换位置次数
        //通过数组中元素相邻元素的比较和位置移动(因为前面的元素是有序的只需整体移动找到e的合适的位置)，找到元素合适的位置

//        T e = arr[i];
//        int j=0;
//        for( j=i ; j > 0 ; j--){
//
//            //寻找元素arr[i]合适的位置
//
//            if (arr[j-1]>e){
//               arr[j]=arr[j-1];  //这里是赋值
//            }else{
//                break;
//            }
//        }
//        arr[j] = e;


        //   加入判断提前  中止循环
        T e = arr[i];
        int j=0;
        for( j=i ; j > 0 & arr[j-1]>e ; j--){
            //寻找元素arr[i]合适的位置
               arr[j]=arr[j-1];
        }
        arr[j]=e;
    }
}

template <typename T>
void bubbleSort(T arr[] , int n){

  //  R（l..n)是待排序的文件，采用自下向上扫描，对R做冒泡排序
    long tmp = 0L;
    for(int i = 0; i < n - 1; i++) {
        for(int j = 0; j < n - i - 1; j++) {
            if(arr[j] > arr[j + 1]){
                tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
/*
        long tmp = 0L;
    bool isSwap = false;
    for(int i = 0; i < n - 1; i++) {    //有n个数，需要n-1趟

        isSwap = false; //重置 标识位
        for(int j = 0; j < n - i - 1; j++) {
            if(arr[j] > arr[j + 1]){

                tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                isSwap = true;
            }
        }
        if (!isSwap){  //  这一趟内层循环是否发生交换，没有则数组已经有序结束外层循环

            break;
        }
    }*/

}

int main(){

    int n =10000;
    int *arr = SortTestHelper::generateRandomArray(n,0,n);
    //   int *arr = SortTestHelper::genarateNearlyOrderedArray(n,10);
    int *arr2 = SortTestHelper::copyIntArray(arr,n);
    int *arr3 = SortTestHelper::copyIntArray(arr,n);

    SortTestHelper::testSort("insertSort",insertSort,arr,n);
    SortTestHelper::testSort("selectSort",selectionSort,arr2,n);
    SortTestHelper::testSort("bubableSort",bubbleSort,arr3,n);

    delete[] arr,arr2,arr3;

    return 0;


}


